package leetcode_cn;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * 求众数
 *
 * @author briarbear
 * @blog https://briarbear.github.io
 * @date 2018-09-04 15:02
 */
public class MajorityElement {

    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int len = nums.length;
        int num;
        for (int i = 0; i < len; i++) {
            if (map.containsKey(nums[i])){
                num = map.get(nums[i]);
                if (num+1 > len/2) return nums[i];
                map.put(nums[i],num+1);
            }else {
                map.put(nums[i],1);
            }
        }

        return nums[0];
    }

    public int solution(int[] nums){
        if (nums == null || nums.length == 0) return 0;
        int res = 0,count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                count++;
                res = nums[i];
                continue;
            }else {
                if (nums[i] == res) count++;
                else count--;
            }
        }

        return res;
    }
}
